package com.cqs.leetcode;


import java.util.*;

public class IntersectionofTwoArrays321 {


    //letcode 1ms
    public int[] intersection2(int[] nums1, int[] nums2) {
        if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) return new int[0];
        int n1 = nums1.length;
        int n2 = nums2.length;
        if (n1 > n2) return intersection2(nums2, nums1);
        int min = nums1[0];
        int max = nums1[0];
        for (int a : nums1) {
            if (a > max) max = a;
            if (a < min) min = a;
        }
        boolean[] hash = new boolean[max - min + 1];
        for (int a : nums1) hash[a - min] = true;
        int[] ans = new int[Math.min(max - min + 1, n2)];
        int k = 0;
        for (int a : nums2) {
            if (a < min || a > max) continue;
            if (hash[a - min]) {
                hash[a - min] = false;
                ans[k++] = a;
            }
        }
        return Arrays.copyOf(ans, k);
    }

    //7ms
    public int[] intersection1(int[] nums1, int[] nums2) {
        if (nums1 == null || nums2 == null || nums1.length == 0 || nums2.length == 0) return new int[0];
        Set<Integer> set1 = new HashSet<>();//保存短数组的元素
        Set<Integer> set2 = new HashSet<>();//保留结果元素
        if (nums2.length < nums1.length) {
            int[] tmp = nums1;
            nums1 = nums2;
            nums2 = tmp;
        }
        for (int i : nums1) {
            set1.add(i);
        }
        for (int i = 0; i < nums2.length; i++) {
            if (set1.contains(nums2[i])) {
                //保留至结果集中
                set2.add(nums2[i]);
                //从set1中删除 不用在再比较了
                set1.remove(nums2[i]);
            }
        }
        //转化成数组
        int[] result = new int[set2.size()];
        Iterator<Integer> iterator = set2.iterator();
        int count = -1;
        while (iterator.hasNext()) {
            result[++count] = iterator.next();
        }
        return result;
    }

    //2ms
    public int[] intersection(int[] nums1, int[] nums2) {
        if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) return new int[0];
        BitSet bs = new BitSet();
        //num1是长度较短的数组
        if (nums2.length < nums1.length) {
            int[] tmp = nums1;
            nums1 = nums2;
            nums2 = tmp;
        }
        for (int i : nums1) {
            bs.set(i);
        }
        //结果集最大的数组空间
        int[] result = new int[nums1.length];
        //结果集的实际大小
        int count = 0;
        for (int i : nums2) {
            if (bs.get(i)) {
                //去重
                bs.set(i, false);
                result[count++] = i;
            }
        }
        return Arrays.copyOf(result, count);
    }

    public static void main(String[] args) {
        int[] array = new int[]{1, 2, 3, 64<<4, 0, 3};
        BitSet bitSet = new BitSet(6);
        //将数组内容组bitmap
        for (int i = 0; i < array.length; i++) {
            bitSet.set(array[i], true);
        }
        for (int i = 1; i <= 1024; i++) {
            if (i % 8 == 0)
                System.out.println("");
            System.out.print((1<<i) +"\t");
        }
        System.out.println(1L<<1024);
    }
}
